package com.algorithm.array;

import static com.google.common.primitives.Ints.max;

public class MaxBarArea {
    /**
     *@author : daniel.yang
     *@date : 2018/11/13
     *@desc :
    给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
    求在该柱状图中，能够勾勒出来的矩形的最大面积。
     */
    public static void main(String[] args) {
        int[] arr = {2,1,5,6,2,3};
        int maxArea = findMaxArea(arr, 0, arr.length - 1);
        System.out.println(maxArea);
    }

    private static int findMaxArea(int[] arr,int start,int end) {
        if (start >= end){
            return arr[start];
        }else if (start < 0 || end >= arr.length){
            return 0;
        }
        int lowestIndex = findLowestIndex(arr,start,end);
        int leftMax = findMaxArea(arr, start, lowestIndex - 1);
        int rightArea = findMaxArea(arr, lowestIndex + 1, end);
        int thisArea = arr[lowestIndex] * (end - start + 1);
        return max(thisArea, leftMax, rightArea);
    }

    private static int findLowestIndex(int[] arr,int start,int end) {
        int lowIndex = start;
        for (int i = start; i < end; i++) {
            if (arr[i] <arr[lowIndex]) lowIndex = i;
        }
        return lowIndex;
    }
}
